import org.apache.commons.lang3.ArrayUtils;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;

// 排序
public class Sort {
  public static void printArray(int[] arr) {
    System.out.println(ArrayUtils.toString(arr));
  }

  // 交换值
  public static void sawp(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  // 选择排序正排
  public static void selectSortASC(int arr[]) {
    for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
          sawp(arr, i, j);
        }
      }
    }
  }

  // 选择排序倒排：
  public static void selectSortDESC(int arr[]) {
    for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] < arr[j]) {
          sawp(arr, i, j);
        }
      }
    }
  }
  // 冒泡排序正排
  public static void bublleSortASC(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) { // 趟数
      for (int j = 0; j < arr.length - i - 1; j++) { // 比较次数
        if (arr[j] > arr[j + 1]) {
          sawp(arr, j, j + 1);
        }
      }
    }
  }

  // 冒泡排序倒排
  public static void bublleSortDESC(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) { // 趟数
      for (int j = arr.length - 1; j > 0 + i; j--) { // 比较次数
        if (arr[j] < arr[j - 1]) {
          sawp(arr, j, j - 1);
        }
      }
    }
  }

  // 插入排序 第一遍从第二个数下标1拿 依次比较前面的数，  拿到的数比它前面的数小的话 则挪动被比较的数往前面进一位顶替位置 顶替掉被拿位置
  //    第二遍从第三个数下标2拿 依次比较前面的数， 拿到的数比它前面的数小的话 则挪动被比较的数往前面进一位顶替位置
  public static void insertSort(int arr[]) {
    for (int i = 1; i < arr.length; i++) {
      int j = i - 1;
      int temp = arr[i]; // 需要插入的数据
      while (j >= 0 && temp < arr[j]) // 当插入的数据小于前面的数据时
      {
        arr[j + 1] = arr[j]; // 将插入的数据的后面的数据向后移动
        j--;
      }
      arr[++j] = temp; // 插入数据
    }
  }

  // 插入排序 外层遍历范围按 有序区间即[0,arr.length - 2]
  //    static void insertSort2(int arr[]) {
  //        for (int i = 0; i < arr.length - 1; i++) {
  //            int j = i;
  //            int temp = arr[i + 1];//需要插入的数据按有序区间外+1
  //            while (temp < arr[j] && j >= 0)//当插入的数据小于前面的数据时
  //            {
  //                arr[j + 1] = arr[j];//将插入的数据的后面的数据向后移动
  //                j--;
  //            }
  //            arr[++j] = temp;//插入数据
  //        }
  //    }
  // 插入排序 外层遍历范围按 有序区间即[0,arr.length - 2]
  static void insertSort2(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
      int j = i;
      int temp = arr[i + 1]; // 需要插入的数据按有序区间外+1
      while (j > -1 && temp < arr[j]) { // 当插入的数据小于前面的数据时
        arr[j + 1] = arr[j]; // 将插入的数据的后面的数据向后移动
        --j;
      }
      arr[j + 1] = temp; // 插入数据
    }
  }

  //    希尔排序
  static void shellSort(int arr[]) {
    int gap = arr.length;
    int end = 0;
    while (gap > 1) {
      //            步长向下取整
      gap = gap / 3 + 1;
      end = 0;
      //            步长插入 被插入数初始下标位置为end + gap 递增至arr.length-1
      for (int index = end + gap; index < arr.length; ++index) {
        end = index - gap;
        int temp = arr[index];
        while (end >= 0 && arr[end] > temp) {
          arr[end + gap] = arr[end];
          //                    end减去步长作为下一个大小校验位置
          end -= gap;
        }
        arr[end + gap] = temp;
      }
    }
  }

  //    希尔排序
  static void shellSort2(int[] a) {
    int n = a.length;
    int i, j, k, gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
      for (i = 0; i < gap; i++) {
        for (j = i + gap; j < n; j += gap) {
          int temp = a[j];
          for (k = j - gap; k >= 0 && a[k] > temp; k -= gap) {
            a[k + gap] = a[k];
          }
          a[k + gap] = temp;
        }
      }
      printArray(a);
    }
  }

  /**
   * 严格按照定义来写的希尔排序
   *
   * @param a
   */
  static void shellSort3(int[] a) {
    int n = a.length;
    int i, j, k, gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
      for (i = 0; i < gap; i++) {
        for (j = i + gap; j < n; j += gap) {
          int temp = a[j];
          for (k = j - gap; k >= 0 && a[k] > temp; k -= gap) {
            a[k + gap] = a[k];
          }
          a[k + gap] = temp;
        }
      }
      printArray(a);
    }
  }

  /** 19 * 希尔排序 针对有序序列在插入时采用交换法 20 * @param arr 21 */
  public static void sort(int[] arr) {
    // 增量gap，并逐步缩小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
      // 从第gap个元素，逐个对其所在组进行直接插入排序操作
      for (int i = gap; i < arr.length; i++) {
        int j = i;
        while (j - gap >= 0 && arr[j] < arr[j - gap]) {
          // 插入排序采用交换法
          swap(arr, j, j - gap);
          j -= gap;
        }
      }
    }
  }

  /**
   * 希尔排序就是从初始2组到4组2~* 最终为所有元素为同一组 第一层分组,第二层循环走完是用步长同时处理所有组的排序,排序用的冒泡俩数和比较交换法
   *
   * @param arr
   */
  public static void xierSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < arr.length; i++) {
        int j = i;
        while (j - gap >= 0 && arr[j - gap] > arr[j]) {
          // 插入排序采用俩数和处理的交换法
          swap(arr, j, j - gap);
          j -= gap;
        }
      }
    }
  }

  public static void xier2Sort(int[] arr) {

    // 每轮取得/2步长
    for (int i = arr.length / 2; i > 0; i = i / 2) {
      //
      for (int i2 = i; i2 < arr.length; i2++) {
        if (arr[i2] < arr[i2 - i]) {
          int iVar = arr[i2 - i];
          arr[i2 - i] = arr[i2];
          arr[i2] = iVar;
        }
      }
    }
  }

  /** 60 * 交换数组元素 61 * @param arr 62 * @param a 63 * @param b 64 */
  public static void swap(int[] arr, int a, int b) {
    arr[a] = arr[a] + arr[b];
    arr[b] = arr[a] - arr[b];
    arr[a] = arr[a] - arr[b];
  }

  // 二分查找：
  public static void binarySearch(int arr[], int serch) {
    //        int arr[] = {1, 11, 33, 44, 45, 46, 47, 76, 100, 200, 201};
    //        int serch = 201;
    int low = 0;
    int hight = arr.length - 1;
    int mid = (low + hight) / 2;
    while (low <= hight) {
      if (serch > arr[mid]) {
        low = mid + 1;
        mid = (low + hight) / 2;
      } else if (serch < arr[mid]) {
        hight = mid - 1;
        mid = (low + hight) / 2;
      } else {
        System.out.print("二分查找到：" + mid);
        break;
      }
    }
  }

  public static void main(String args[]) {
    int arr[] = {6, 9, 8, 4, 10, 0, 3, 1, 5, 7, 2, 13, 12, 17, 11, 14, 16};
    //    xierSort2(arr);
    //    xierSort(arr);
    //    //    sort(arr);
    //    for (int i = 0; i < arr.length; i++) {
    //      int res = arr[i];
    //      System.out.println(res);
    //    }
    //        selectSort(arr);
    //        bublleSort(arr);
    //        bublleSort2(arr);
    //        insertSort(arr);
    //        insertSort2(arr);
    //        shellSort(arr);
    //        shellSort2(arr);
    //    shellSort3(arr);
    //    int serch = 7;
    //    binarySearch(arr, serch);

    xierSort2(arr);
    printArray(arr);
  }

  public static <K extends Comparable, V extends Comparable> Map<K, V> sortMapByValues(
      Map<K, V> aMap) {
    HashMap<K, V> finalOut = new LinkedHashMap<>();
    aMap.entrySet().stream()
        .sorted((p1, p2) -> p2.getValue().compareTo(p1.getValue()))
        .collect(Collectors.toList())
        .forEach(ele -> finalOut.put(ele.getKey(), ele.getValue()));
    return finalOut;
  }
  /**/
  public static void xierSort2(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < arr.length; i++) {
        int j = i;
        int current = arr[i];
        while (j - gap >= 0 && current < arr[j - gap]) {
          arr[j] = arr[j - gap];
          j = j - gap;
        }
        arr[j] = current;
      }
    }
  }

  public static void xierSort3(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
      for (int i = gap; i < arr.length; i++) {
        int j = i;
      }
    }
  }
}
